/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-05-16
 * Time: 9:37
 */
class Solution3 {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int x : nums) {
            sum += x;
        }
        int a = (sum+target) / 2;

        if((sum+target) % 2 == 1 || a < 0) {
            return 0;
        }
        //前i个位置选中和为j的选法个数
        int[][] dp = new int[n+1][a+1];

        dp[0][0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= a; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1]) {
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][a];
    }
}

/* 优化后
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int x : nums) {
            sum += x;
        }
        int a = (sum+target) / 2;

        if((sum+target) % 2 == 1 || a < 0) {
            return 0;
        }
        //前i个位置选中和为j的选法个数
        int[] dp = new int[a+1];

        dp[0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = a; j >= nums[i-1]; j--) {
                dp[j] += dp[j-nums[i-1]];
            }
        }
        return dp[a];
    }
}*/
